From 5851827379a4bf32caf43af3ad8505c3d18b133c Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Fri, 17 Oct 2014 08:17:17 -0700 Subject: [PATCH] Implement resolution of version requirements This commit extends the support in cargo's resolver to start resolving packages with multiple versions as well as package requirements. This is a crucial step forward when impelmenting the cargo registry as multiple versions will be uploaded to the registry quite quickly! This implements a fairly naive solution which should at least help cargo get out the gates initially. This impelments a depth-first-search of the pacakage dependency graph with a few sorting heuristics along the way to help out resolution as it goes along. Resolution errors will likely improve over time, but this commit does make an effort to try to get some good error messages right off the bat. --- Cargo.toml | 3 + Makefile.in | 2 +- src/cargo/core/resolver/mod.rs | 489 +++++++++++++-------------------- src/cargo/core/summary.rs | 8 +- src/cargo/util/graph.rs | 6 + tests/resolve.rs | 357 ++++++++++++++++++++++++ tests/test_cargo_compile.rs | 10 +- tests/test_cargo_registry.rs | 12 +- 8 files changed, 575 insertions(+), 312 deletions(-) create mode 100644 tests/resolve.rs diff --git a/Cargo.toml b/Cargo.toml index b6e0d6e9d..a397a6a66 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -46,3 +46,6 @@ doc = false [[test]] name = "tests" + +[[test]] +name = "resolve" diff --git a/Makefile.in b/Makefile.in index 73aedcaf2..4b09b9ec7 100644 --- a/Makefile.in +++ b/Makefile.in @@ -89,7 +89,7 @@ style: sh tests/check-style.sh no-exes: - find $$(git ls-files | grep -v ttf) -perm +111 -type f \ + find $$(git ls-files) -perm +111 -type f \ -not -name configure -not -name '*.sh' -not -name '*.rs' | \ grep '.*' \ && exit 1 || exit 0 diff --git a/src/cargo/core/resolver/mod.rs b/src/cargo/core/resolver/mod.rs index dbec2bf6b..f400ccf90 100644 --- a/src/cargo/core/resolver/mod.rs +++ b/src/cargo/core/resolver/mod.rs @@ -3,7 +3,7 @@ use std::fmt; use core::{PackageId, Registry, SourceId, Summary, Dependency}; use core::PackageIdSpec; -use util::{CargoResult, Graph, human, internal, ChainError}; +use util::{CargoResult, Graph, human, ChainError}; use util::profile; use util::graph::{Nodes, Edges}; @@ -16,7 +16,7 @@ mod encode; /// /// Each instance of `Resolve` also understands the full set of features used /// for each package as well as what the root package is. -#[deriving(PartialEq, Eq)] +#[deriving(PartialEq, Eq, Clone)] pub struct Resolve { graph: Graph, features: HashMap>, @@ -109,133 +109,214 @@ impl fmt::Show for Resolve { } } -struct Context<'a, R:'a> { - registry: &'a mut R, +#[deriving(Clone)] +struct Context { + activations: HashMap<(String, SourceId), Vec>, resolve: Resolve, - // cycle detection visited: HashSet, - - // Try not to re-resolve too much - resolved: HashMap>, - - // Eventually, we will have smarter logic for checking for conflicts in the - // resolve, but without the registry, conflicts should not exist in - // practice, so this is just a sanity check. - seen: HashMap<(String, SourceId), semver::Version>, -} - -impl<'a, R: Registry> Context<'a, R> { - fn new(registry: &'a mut R, root: PackageId) -> Context<'a, R> { - Context { - registry: registry, - resolve: Resolve::new(root), - seen: HashMap::new(), - visited: HashSet::new(), - resolved: HashMap::new(), - } - } } /// Builds the list of all packages required to build the first argument. pub fn resolve(summary: &Summary, method: ResolveMethod, registry: &mut R) -> CargoResult { log!(5, "resolve; summary={}", summary); + + let mut cx = Context { + resolve: Resolve::new(summary.get_package_id().clone()), + activations: HashMap::new(), + visited: HashSet::new(), + }; let _p = profile::start(format!("resolving: {}", summary)); + cx.activations.insert((summary.get_name().to_string(), + summary.get_source_id().clone()), + vec![summary.clone()]); + match try!(activate(cx, registry, summary, method)) { + Ok(cx) => Ok(cx.resolve), + Err(e) => Err(e), + } +} - let mut context = Context::new(registry, summary.get_package_id().clone()); - context.seen.insert((summary.get_name().to_string(), - summary.get_source_id().clone()), - summary.get_version().clone()); - try!(resolve_deps(summary, method, &mut context)); - log!(5, " result={}", context.resolve); - Ok(context.resolve) +fn activate(mut cx: Context, + registry: &mut R, + parent: &Summary, + method: ResolveMethod) + -> CargoResult> { + // First, figure out our set of dependencies based on the requsted set of + // features. This also calculates what features we're going to enable for + // our own dependencies. + let deps = try!(resolve_features(&mut cx, parent, method)); + + // Next, transform all dependencies into a list of possible candidates which + // can satisfy that dependency. + let mut deps = try!(deps.into_iter().map(|(_dep_name, (dep, features))| { + let mut candidates = try!(registry.query(dep)); + // When we attempt versions for a package, we'll want to start at the + // maximum version and work our way down. + candidates.as_mut_slice().sort_by(|a, b| { + b.get_version().cmp(a.get_version()) + }); + Ok((dep, candidates, features)) + }).collect::>>()); + + // When we recurse, attempt to resolve dependencies with fewer candidates + // before recursing on dependencies with more candidates. This way if the + // dependency with only one candidate can't be resolved we don't have to do + // a bunch of work before we figure that out. + deps.as_mut_slice().sort_by(|&(_, ref a, _), &(_, ref b, _)| { + a.len().cmp(&b.len()) + }); + + activate_deps(cx, registry, parent, deps.as_slice(), 0) } -fn resolve_deps<'a, R: Registry>(parent: &Summary, - method: ResolveMethod, - ctx: &mut Context<'a, R>) - -> CargoResult<()> { - let (deps, features) = try!(resolve_features(parent, method, ctx)); +fn activate_deps(cx: Context, + registry: &mut R, + parent: &Summary, + deps: &[(&Dependency, Vec, Vec)], + cur: uint) -> CargoResult> { + if cur == deps.len() { return Ok(Ok(cx)) } + let (dep, ref candidates, ref features) = deps[cur]; + let method = ResolveRequired(false, features.as_slice(), + dep.uses_default_features()); + + let key = (dep.get_name().to_string(), dep.get_source_id().clone()); + let prev_active = cx.activations.find(&key) + .map(|v| v.as_slice()).unwrap_or(&[]); + log!(5, "{}[{}]>{} {} candidates", parent.get_name(), cur, dep.get_name(), + candidates.len()); + log!(5, "{}[{}]>{} {} prev activations", parent.get_name(), cur, + dep.get_name(), prev_active.len()); + + // Filter the set of candidates based on the previously activated + // versions for this dependency. We can actually use a version if it + // precisely matches an activated version or if it is otherwise + // incompatible with all other activated versions. Note that we define + // "compatible" here in terms of the semver sense where if the left-most + // nonzero digit is the same they're considered compatible. + let mut my_candidates = candidates.iter().filter(|&b| { + prev_active.iter().any(|a| a == b) || + prev_active.iter().all(|a| { + !compatible(a.get_version(), b.get_version()) + }) + }); + + // Alright, for each candidate that's gotten this far, it meets the + // following requirements: + // + // 1. The version matches the dependency requirement listed for this + // package + // 2. There are no activated versions for this package which are + // semver-compatible, or there's an activated version which is + // precisely equal to `candidate`. + // + // This means that we're going to attempt to activate each candidate in + // turn. We could possibly fail to activate each candidate, so we try + // each one in turn. + let mut last_err = None; + for candidate in my_candidates { + log!(5, "{}[{}]>{} trying {}", parent.get_name(), cur, dep.get_name(), + candidate.get_version()); + let mut my_cx = cx.clone(); + { + my_cx.resolve.graph.link(parent.get_package_id().clone(), + candidate.get_package_id().clone()); + let prev = match my_cx.activations.entry(key.clone()) { + Occupied(e) => e.into_mut(), + Vacant(e) => e.set(Vec::new()), + }; + if !prev.iter().any(|c| c == candidate) { + my_cx.resolve.graph.add(candidate.get_package_id().clone(), []); + prev.push(candidate.clone()); - // Recursively resolve all dependencies - for &dep in deps.iter() { - if !match ctx.resolved.entry(parent.get_package_id().clone()) { - Occupied(entry) => entry.into_mut(), - Vacant(entry) => entry.set(HashSet::new()), - }.insert(dep.get_name().to_string()) { - continue - } - - let pkgs = try!(ctx.registry.query(dep)); - if pkgs.is_empty() { - return Err(human(format!("No package named `{}` found \ - (required by `{}`).\n\ - Location searched: {}\n\ - Version required: {}", - dep.get_name(), - parent.get_package_id().get_name(), - dep.get_source_id(), - dep.get_version_req()))); - } else if pkgs.len() > 1 { - return Err(internal(format!("At the moment, Cargo only supports a \ - single source for a particular package name ({}).", dep))); - } + } - let summary = &pkgs[0]; - let name = summary.get_name().to_string(); - let source_id = summary.get_source_id().clone(); - let version = summary.get_version(); - - ctx.resolve.graph.link(parent.get_package_id().clone(), - summary.get_package_id().clone()); - - let found = match ctx.seen.find(&(name.clone(), source_id.clone())) { - Some(v) if v == version => true, - Some(..) => { - return Err(human(format!("Cargo found multiple copies of {} in \ - {}. This is not currently supported", - summary.get_name(), - summary.get_source_id()))); + // Dependency graphs are required to be a DAG. Non-transitive + // dependencies (dev-deps), however, can never introduce a cycle, so we + // skip them. + if dep.is_transitive() && + !my_cx.visited.insert(candidate.get_package_id().clone()) { + return Err(human(format!("cyclic package dependency: package `{}` \ + depends on itself", + candidate.get_package_id()))) } - None => false, + } + let mut my_cx = match try!(activate(my_cx, registry, candidate, method)) { + Ok(cx) => cx, + Err(e) => { last_err = Some(e); continue } }; - if !found { - ctx.seen.insert((name, source_id), version.clone()); - ctx.resolve.graph.add(summary.get_package_id().clone(), []); + if dep.is_transitive() { + my_cx.visited.remove(candidate.get_package_id()); } - - // Dependency graphs are required to be a DAG. Non-transitive - // dependencies (dev-deps), however, can never introduce a cycle, so we - // skip them. - if dep.is_transitive() && - !ctx.visited.insert(summary.get_package_id().clone()) { - return Err(human(format!("Cyclic package dependency: package `{}` \ - depends on itself", - summary.get_package_id()))) + match try!(activate_deps(my_cx, registry, parent, deps, cur + 1)) { + Ok(cx) => return Ok(Ok(cx)), + Err(e) => { last_err = Some(e); } } + } + log!(5, "{}[{}]>{} -- {}", parent.get_name(), cur, dep.get_name(), last_err); + + // Oh well, we couldn't activate any of the candidates, so we just can't + // activate this dependency at all + Ok(match last_err { + Some(e) => Err(e), + None if candidates.len() > 0 => { + let mut msg = format!("failed to select a version for `{}` \ + (required by `{}`):\n\ + all possible versions conflict with \ + previously selected versions of `{}`", + dep.get_name(), parent.get_name(), + dep.get_name()); + 'outer: for v in prev_active.iter() { + for node in cx.resolve.graph.iter() { + let mut edges = match cx.resolve.graph.edges(node) { + Some(edges) => edges, + None => continue, + }; + for edge in edges { + if edge != v.get_package_id() { continue } + + msg.push_str(format!("\n version {} in use by {}", + v.get_version(), edge).as_slice()); + continue 'outer; + } + } + msg.push_str(format!("\n version {} in use by ??", + v.get_version()).as_slice()); + } - // The list of enabled features for this dependency are both those - // listed in the dependency itself as well as any of our own features - // which enabled a feature of this package. - let features = features.find_equiv(&dep.get_name()) - .map(|v| v.as_slice()) - .unwrap_or(&[]); - try!(resolve_deps(summary, - ResolveRequired(false, features, - dep.uses_default_features()), - ctx)); - if dep.is_transitive() { - ctx.visited.remove(summary.get_package_id()); + msg.push_str(format!("\n possible versions to select: {}", + candidates.iter().map(|v| v.get_version()) + .collect::>()).as_slice()); + + Err(human(msg)) } - } + None => { + Err(human(format!("no package named `{}` found (required by `{}`)\n\ + location searched: {}\n\ + version required: {}", + dep.get_name(), parent.get_name(), + dep.get_source_id(), + dep.get_version_req()))) + } + }) +} - Ok(()) +// Returns if `a` and `b` are compatible in the semver sense. This is a +// commutative operation. +// +// Versions `a` and `b` are compatible if their left-most nonzero digit is the +// same. +fn compatible(a: &semver::Version, b: &semver::Version) -> bool { + if a.major != b.major { return false } + if a.major != 0 { return true } + if a.minor != b.minor { return false } + if a.minor != 0 { return true } + a.patch == b.patch } -fn resolve_features<'a, R>(parent: &'a Summary, method: ResolveMethod, - ctx: &mut Context) - -> CargoResult<(Vec<&'a Dependency>, - HashMap<&'a str, Vec>)> { +fn resolve_features<'a>(cx: &mut Context, parent: &'a Summary, + method: ResolveMethod) + -> CargoResult)>> { let dev_deps = match method { ResolveEverything => true, ResolveRequired(dev_deps, _, _) => dev_deps, @@ -266,7 +347,7 @@ fn resolve_features<'a, R>(parent: &'a Summary, method: ResolveMethod, feature))); } } - ret.insert(dep.get_name(), base); + ret.insert(dep.get_name(), (*dep, base)); } // All features can only point to optional dependencies, in which case they @@ -286,13 +367,13 @@ fn resolve_features<'a, R>(parent: &'a Summary, method: ResolveMethod, // Record what list of features is active for this package. { let pkgid = parent.get_package_id().clone(); - match ctx.resolve.features.entry(pkgid) { + match cx.resolve.features.entry(pkgid) { Occupied(entry) => entry.into_mut(), Vacant(entry) => entry.set(HashSet::new()), }.extend(used_features.into_iter()); } - Ok((deps, ret)) + Ok(ret) } // Returns a pair of (feature dependencies, all used features) @@ -384,193 +465,3 @@ fn build_features(s: &Summary, method: ResolveMethod) Ok(()) } } - -#[cfg(test)] -mod test { - use std::collections::HashMap; - - use hamcrest::{assert_that, equal_to, contains}; - - use core::source::{SourceId, RegistryKind, GitKind}; - use core::{Dependency, PackageId, Summary, Registry}; - use util::{CargoResult, ToUrl}; - - fn resolve(pkg: PackageId, deps: Vec, - registry: &mut R) - -> CargoResult> { - let summary = Summary::new(pkg, deps, HashMap::new()).unwrap(); - let method = super::ResolveEverything; - Ok(try!(super::resolve(&summary, method, - registry)).iter().map(|p| p.clone()).collect()) - } - - trait ToDep { - fn to_dep(self) -> Dependency; - } - - impl ToDep for &'static str { - fn to_dep(self) -> Dependency { - let url = "http://example.com".to_url().unwrap(); - let source_id = SourceId::new(RegistryKind, url); - Dependency::parse(self, Some("1.0.0"), &source_id).unwrap() - } - } - - impl ToDep for Dependency { - fn to_dep(self) -> Dependency { - self - } - } - - macro_rules! pkg( - ($name:expr => $($deps:expr),+) => ({ - let d: Vec = vec!($($deps.to_dep()),+); - - Summary::new(PackageId::new($name, "1.0.0", ®istry_loc()).unwrap(), - d, HashMap::new()).unwrap() - }); - - ($name:expr) => ( - Summary::new(PackageId::new($name, "1.0.0", ®istry_loc()).unwrap(), - Vec::new(), HashMap::new()).unwrap() - ) - ) - - fn registry_loc() -> SourceId { - let remote = "http://example.com".to_url().unwrap(); - SourceId::new(RegistryKind, remote) - } - - fn pkg(name: &str) -> Summary { - Summary::new(pkg_id(name), Vec::new(), HashMap::new()).unwrap() - } - - fn pkg_id(name: &str) -> PackageId { - PackageId::new(name, "1.0.0", ®istry_loc()).unwrap() - } - - fn pkg_id_loc(name: &str, loc: &str) -> PackageId { - let remote = loc.to_url(); - let source_id = SourceId::new(GitKind("master".to_string()), - remote.unwrap()); - - PackageId::new(name, "1.0.0", &source_id).unwrap() - } - - fn pkg_loc(name: &str, loc: &str) -> Summary { - Summary::new(pkg_id_loc(name, loc), Vec::new(), HashMap::new()).unwrap() - } - - fn dep(name: &str) -> Dependency { - let url = "http://example.com".to_url().unwrap(); - let source_id = SourceId::new(RegistryKind, url); - Dependency::parse(name, Some("1.0.0"), &source_id).unwrap() - } - - fn dep_loc(name: &str, location: &str) -> Dependency { - let url = location.to_url().unwrap(); - let source_id = SourceId::new(GitKind("master".to_string()), url); - Dependency::parse(name, Some("1.0.0"), &source_id).unwrap() - } - - fn registry(pkgs: Vec) -> Vec { - pkgs - } - - fn names(names: &[&'static str]) -> Vec { - names.iter() - .map(|name| PackageId::new(*name, "1.0.0", ®istry_loc()).unwrap()) - .collect() - } - - fn loc_names(names: &[(&'static str, &'static str)]) -> Vec { - names.iter() - .map(|&(name, loc)| pkg_id_loc(name, loc)).collect() - } - - #[test] - pub fn test_resolving_empty_dependency_list() { - let res = resolve(pkg_id("root"), Vec::new(), - &mut registry(vec!())).unwrap(); - - assert_that(&res, equal_to(&names(["root"]))); - } - - #[test] - pub fn test_resolving_only_package() { - let mut reg = registry(vec!(pkg("foo"))); - let res = resolve(pkg_id("root"), vec![dep("foo")], &mut reg); - - assert_that(&res.unwrap(), contains(names(["root", "foo"])).exactly()); - } - - #[test] - pub fn test_resolving_one_dep() { - let mut reg = registry(vec!(pkg("foo"), pkg("bar"))); - let res = resolve(pkg_id("root"), vec![dep("foo")], &mut reg); - - assert_that(&res.unwrap(), contains(names(["root", "foo"])).exactly()); - } - - #[test] - pub fn test_resolving_multiple_deps() { - let mut reg = registry(vec!(pkg!("foo"), pkg!("bar"), pkg!("baz"))); - let res = resolve(pkg_id("root"), vec![dep("foo"), dep("baz")], - &mut reg).unwrap(); - - assert_that(&res, contains(names(["root", "foo", "baz"])).exactly()); - } - - #[test] - pub fn test_resolving_transitive_deps() { - let mut reg = registry(vec!(pkg!("foo"), pkg!("bar" => "foo"))); - let res = resolve(pkg_id("root"), vec![dep("bar")], &mut reg).unwrap(); - - assert_that(&res, contains(names(["root", "foo", "bar"]))); - } - - #[test] - pub fn test_resolving_common_transitive_deps() { - let mut reg = registry(vec!(pkg!("foo" => "bar"), pkg!("bar"))); - let res = resolve(pkg_id("root"), vec![dep("foo"), dep("bar")], - &mut reg).unwrap(); - - assert_that(&res, contains(names(["root", "foo", "bar"]))); - } - - #[test] - pub fn test_resolving_with_same_name() { - let list = vec![pkg_loc("foo", "http://first.example.com"), - pkg_loc("bar", "http://second.example.com")]; - - let mut reg = registry(list); - let res = resolve(pkg_id("root"), - vec![dep_loc("foo", "http://first.example.com"), - dep_loc("bar", "http://second.example.com")], - &mut reg); - - let mut names = loc_names([("foo", "http://first.example.com"), - ("bar", "http://second.example.com")]); - - names.push(pkg_id("root")); - - assert_that(&res.unwrap(), contains(names).exactly()); - } - - #[test] - pub fn test_resolving_with_dev_deps() { - let mut reg = registry(vec!( - pkg!("foo" => "bar", dep("baz").transitive(false)), - pkg!("baz" => "bat", dep("bam").transitive(false)), - pkg!("bar"), - pkg!("bat") - )); - - let res = resolve(pkg_id("root"), - vec![dep("foo"), dep("baz").transitive(false)], - &mut reg).unwrap(); - - assert_that(&res, contains(names(["root", "foo", "bar", "baz"]))); - } -} - diff --git a/src/cargo/core/summary.rs b/src/cargo/core/summary.rs index b794f8db4..04abb7eb8 100644 --- a/src/cargo/core/summary.rs +++ b/src/cargo/core/summary.rs @@ -8,7 +8,7 @@ use util::{CargoResult, human}; /// Subset of a `Manifest`. Contains only the most important informations about a package. /// /// Summaries are cloned, and should not be mutated after creation -#[deriving(Show,Clone,PartialEq)] +#[deriving(Show,Clone)] pub struct Summary { package_id: PackageId, dependencies: Vec, @@ -91,6 +91,12 @@ impl Summary { } } +impl PartialEq for Summary { + fn eq(&self, other: &Summary) -> bool { + self.package_id == other.package_id + } +} + pub trait SummaryVec { fn names(&self) -> Vec; } diff --git a/src/cargo/util/graph.rs b/src/cargo/util/graph.rs index b83e4a8e9..5473b0b34 100644 --- a/src/cargo/util/graph.rs +++ b/src/cargo/util/graph.rs @@ -92,3 +92,9 @@ impl PartialEq for Graph { fn eq(&self, other: &Graph) -> bool { self.nodes.eq(&other.nodes) } } impl Eq for Graph {} + +impl Clone for Graph { + fn clone(&self) -> Graph { + Graph { nodes: self.nodes.clone() } + } +} diff --git a/tests/resolve.rs b/tests/resolve.rs new file mode 100644 index 000000000..aa0728819 --- /dev/null +++ b/tests/resolve.rs @@ -0,0 +1,357 @@ +#![feature(macro_rules)] + +extern crate hamcrest; +extern crate cargo; + +use std::collections::HashMap; + +use hamcrest::{assert_that, equal_to, contains}; + +use cargo::core::source::{SourceId, RegistryKind, GitKind}; +use cargo::core::{Dependency, PackageId, Summary, Registry}; +use cargo::util::{CargoResult, ToUrl}; +use cargo::core::resolver::{mod, ResolveEverything}; + +fn resolve(pkg: PackageId, deps: Vec, + registry: &mut R) + -> CargoResult> { + let summary = Summary::new(pkg, deps, HashMap::new()).unwrap(); + let method = ResolveEverything; + Ok(try!(resolver::resolve(&summary, method, registry)).iter().map(|p| { + p.clone() + }).collect()) +} + +trait ToDep { + fn to_dep(self) -> Dependency; +} + +impl ToDep for &'static str { + fn to_dep(self) -> Dependency { + let url = "http://example.com".to_url().unwrap(); + let source_id = SourceId::new(RegistryKind, url); + Dependency::parse(self, Some("1.0.0"), &source_id).unwrap() + } +} + +impl ToDep for Dependency { + fn to_dep(self) -> Dependency { + self + } +} + +trait ToPkgId { + fn to_pkgid(&self) -> PackageId; +} + +impl ToPkgId for &'static str { + fn to_pkgid(&self) -> PackageId { + PackageId::new(*self, "1.0.0", ®istry_loc()).unwrap() + } +} + +impl ToPkgId for (&'static str, &'static str) { + fn to_pkgid(&self) -> PackageId { + let (name, vers) = *self; + PackageId::new(name, vers, ®istry_loc()).unwrap() + } +} + +macro_rules! pkg( + ($pkgid:expr => [$($deps:expr),+]) => ({ + let d: Vec = vec![$($deps.to_dep()),+]; + + Summary::new($pkgid.to_pkgid(), d, HashMap::new()).unwrap() + }); + + ($pkgid:expr) => ( + Summary::new($pkgid.to_pkgid(), Vec::new(), HashMap::new()).unwrap() + ) +) + +fn registry_loc() -> SourceId { + let remote = "http://example.com".to_url().unwrap(); + SourceId::new(RegistryKind, remote) +} + +fn pkg(name: &str) -> Summary { + Summary::new(pkg_id(name), Vec::new(), HashMap::new()).unwrap() +} + +fn pkg_id(name: &str) -> PackageId { + PackageId::new(name, "1.0.0", ®istry_loc()).unwrap() +} + +fn pkg_id_loc(name: &str, loc: &str) -> PackageId { + let remote = loc.to_url(); + let source_id = SourceId::new(GitKind("master".to_string()), + remote.unwrap()); + + PackageId::new(name, "1.0.0", &source_id).unwrap() +} + +fn pkg_loc(name: &str, loc: &str) -> Summary { + Summary::new(pkg_id_loc(name, loc), Vec::new(), HashMap::new()).unwrap() +} + +fn dep(name: &str) -> Dependency { dep_req(name, "1.0.0") } +fn dep_req(name: &str, req: &str) -> Dependency { + let url = "http://example.com".to_url().unwrap(); + let source_id = SourceId::new(RegistryKind, url); + Dependency::parse(name, Some(req), &source_id).unwrap() +} + +fn dep_loc(name: &str, location: &str) -> Dependency { + let url = location.to_url().unwrap(); + let source_id = SourceId::new(GitKind("master".to_string()), url); + Dependency::parse(name, Some("1.0.0"), &source_id).unwrap() +} + +fn registry(pkgs: Vec) -> Vec { + pkgs +} + +fn names(names: &[P]) -> Vec { + names.iter().map(|name| name.to_pkgid()).collect() +} + +fn loc_names(names: &[(&'static str, &'static str)]) -> Vec { + names.iter() + .map(|&(name, loc)| pkg_id_loc(name, loc)).collect() +} + +#[test] +fn test_resolving_empty_dependency_list() { + let res = resolve(pkg_id("root"), Vec::new(), + &mut registry(vec!())).unwrap(); + + assert_that(&res, equal_to(&names(["root"]))); +} + +#[test] +fn test_resolving_only_package() { + let mut reg = registry(vec!(pkg("foo"))); + let res = resolve(pkg_id("root"), vec![dep("foo")], &mut reg); + + assert_that(&res.unwrap(), contains(names(["root", "foo"])).exactly()); +} + +#[test] +fn test_resolving_one_dep() { + let mut reg = registry(vec!(pkg("foo"), pkg("bar"))); + let res = resolve(pkg_id("root"), vec![dep("foo")], &mut reg); + + assert_that(&res.unwrap(), contains(names(["root", "foo"])).exactly()); +} + +#[test] +fn test_resolving_multiple_deps() { + let mut reg = registry(vec!(pkg!("foo"), pkg!("bar"), pkg!("baz"))); + let res = resolve(pkg_id("root"), vec![dep("foo"), dep("baz")], + &mut reg).unwrap(); + + assert_that(&res, contains(names(["root", "foo", "baz"])).exactly()); +} + +#[test] +fn test_resolving_transitive_deps() { + let mut reg = registry(vec!(pkg!("foo"), pkg!("bar" => ["foo"]))); + let res = resolve(pkg_id("root"), vec![dep("bar")], &mut reg).unwrap(); + + assert_that(&res, contains(names(["root", "foo", "bar"]))); +} + +#[test] +fn test_resolving_common_transitive_deps() { + let mut reg = registry(vec!(pkg!("foo" => ["bar"]), pkg!("bar"))); + let res = resolve(pkg_id("root"), vec![dep("foo"), dep("bar")], + &mut reg).unwrap(); + + assert_that(&res, contains(names(["root", "foo", "bar"]))); +} + +#[test] +fn test_resolving_with_same_name() { + let list = vec![pkg_loc("foo", "http://first.example.com"), + pkg_loc("bar", "http://second.example.com")]; + + let mut reg = registry(list); + let res = resolve(pkg_id("root"), + vec![dep_loc("foo", "http://first.example.com"), + dep_loc("bar", "http://second.example.com")], + &mut reg); + + let mut names = loc_names([("foo", "http://first.example.com"), + ("bar", "http://second.example.com")]); + + names.push(pkg_id("root")); + + assert_that(&res.unwrap(), contains(names).exactly()); +} + +#[test] +fn test_resolving_with_dev_deps() { + let mut reg = registry(vec!( + pkg!("foo" => ["bar", dep("baz").transitive(false)]), + pkg!("baz" => ["bat", dep("bam").transitive(false)]), + pkg!("bar"), + pkg!("bat") + )); + + let res = resolve(pkg_id("root"), + vec![dep("foo"), dep("baz").transitive(false)], + &mut reg).unwrap(); + + assert_that(&res, contains(names(["root", "foo", "bar", "baz"]))); +} + +#[test] +fn resolving_with_many_versions() { + let mut reg = registry(vec!( + pkg!(("foo", "1.0.1")), + pkg!(("foo", "1.0.2")), + )); + + let res = resolve(pkg_id("root"), vec![dep("foo")], &mut reg).unwrap(); + + assert_that(&res, contains(names([("root", "1.0.0"), + ("foo", "1.0.2")]))); +} + +#[test] +fn resolving_with_specific_version() { + let mut reg = registry(vec!( + pkg!(("foo", "1.0.1")), + pkg!(("foo", "1.0.2")), + )); + + let res = resolve(pkg_id("root"), vec![dep_req("foo", "=1.0.1")], + &mut reg).unwrap(); + + assert_that(&res, contains(names([("root", "1.0.0"), + ("foo", "1.0.1")]))); +} + +#[test] +fn resolving_incompat_versions() { + let mut reg = registry(vec!( + pkg!(("foo", "1.0.1")), + pkg!(("foo", "1.0.2")), + pkg!("bar" => [dep_req("foo", "=1.0.2")]), + )); + + assert!(resolve(pkg_id("root"), vec![ + dep_req("foo", "=1.0.1"), + dep("bar"), + ], &mut reg).is_err()); +} + +#[test] +fn resolving_backtrack() { + let mut reg = registry(vec!( + pkg!(("foo", "1.0.2") => [dep("bar")]), + pkg!(("foo", "1.0.1") => [dep("baz")]), + pkg!("bar" => [dep_req("foo", "=2.0.2")]), + pkg!("baz"), + )); + + let res = resolve(pkg_id("root"), vec![ + dep_req("foo", "^1"), + ], &mut reg).unwrap(); + + assert_that(&res, contains(names([("root", "1.0.0"), + ("foo", "1.0.1"), + ("baz", "1.0.0")]))); +} + +#[test] +fn resolving_allows_multiple_compatible_versions() { + let mut reg = registry(vec!( + pkg!(("foo", "1.0.0")), + pkg!(("foo", "2.0.0")), + pkg!(("foo", "0.1.0")), + pkg!(("foo", "0.2.0")), + + pkg!("bar" => ["d1", "d2", "d3", "d4"]), + pkg!("d1" => [dep_req("foo", "1")]), + pkg!("d2" => [dep_req("foo", "2")]), + pkg!("d3" => [dep_req("foo", "0.1")]), + pkg!("d4" => [dep_req("foo", "0.2")]), + )); + + let res = resolve(pkg_id("root"), vec![ + dep("bar"), + ], &mut reg).unwrap(); + + assert_that(&res, contains(names([("root", "1.0.0"), + ("foo", "1.0.0"), + ("foo", "2.0.0"), + ("foo", "0.1.0"), + ("foo", "0.2.0"), + ("d1", "1.0.0"), + ("d2", "1.0.0"), + ("d3", "1.0.0"), + ("d4", "1.0.0"), + ("bar", "1.0.0")]))); +} + +#[test] +fn resolving_with_deep_backtracking() { + let mut reg = registry(vec!( + pkg!(("foo", "1.0.1") => [dep_req("bar", "1")]), + pkg!(("foo", "1.0.0") => [dep_req("bar", "2")]), + + pkg!(("bar", "1.0.0") => [dep_req("baz", "=1.0.2"), + dep_req("other", "1")]), + pkg!(("bar", "2.0.0") => [dep_req("baz", "=1.0.1")]), + + pkg!(("baz", "1.0.2") => [dep_req("other", "2")]), + pkg!(("baz", "1.0.1")), + + pkg!(("dep_req", "1.0.0")), + pkg!(("dep_req", "2.0.0")), + )); + + let res = resolve(pkg_id("root"), vec![ + dep_req("foo", "1"), + ], &mut reg).unwrap(); + + assert_that(&res, contains(names([("root", "1.0.0"), + ("foo", "1.0.0"), + ("bar", "2.0.0"), + ("baz", "1.0.1")]))); +} + +#[test] +fn resolving_but_no_exists() { + let mut reg = registry(vec!( + )); + + let res = resolve(pkg_id("root"), vec![ + dep_req("foo", "1"), + ], &mut reg); + assert!(res.is_err()); + + assert_eq!(res.to_string().as_slice(), "Err(\ +no package named `foo` found (required by `root`) +location searched: registry http://example.com/ +version required: ^1\ +)"); +} + +#[test] +fn resolving_cycle() { + let mut reg = registry(vec!( + pkg!("foo" => ["foo"]), + )); + + let res = resolve(pkg_id("root"), vec![ + dep_req("foo", "1"), + ], &mut reg); + assert!(res.is_err()); + + assert_eq!(res.to_string().as_slice(), "Err(\ +cyclic package dependency: package `foo v1.0.0 (registry http://example.com/)` \ +depends on itself\ +)"); +} diff --git a/tests/test_cargo_compile.rs b/tests/test_cargo_compile.rs index 665e91e84..83164d13c 100644 --- a/tests/test_cargo_compile.rs +++ b/tests/test_cargo_compile.rs @@ -501,9 +501,9 @@ test!(cargo_compile_with_dep_name_mismatch { assert_that(p.cargo_process("build"), execs().with_status(101).with_stderr(format!( -r#"No package named `notquitebar` found (required by `foo`). -Location searched: {proj_dir} -Version required: * +r#"no package named `notquitebar` found (required by `foo`) +location searched: {proj_dir} +version required: * "#, proj_dir = p.url()))); }) @@ -1091,8 +1091,8 @@ test!(self_dependency { "#) .file("src/test.rs", "fn main() {}"); assert_that(p.cargo_process("build"), - execs().with_status(0).with_stdout("\ -[..] test v0.0.0 ([..]) + execs().with_status(101).with_stderr("\ +cyclic package dependency: package `test v0.0.0 ([..])` depends on itself ")); }) diff --git a/tests/test_cargo_registry.rs b/tests/test_cargo_registry.rs index 944c25572..2c598c153 100644 --- a/tests/test_cargo_registry.rs +++ b/tests/test_cargo_registry.rs @@ -150,9 +150,9 @@ test!(nonexistent { assert_that(p.cargo_process("build"), execs().with_status(101).with_stderr("\ -No package named `nonexistent` found (required by `foo`). -Location searched: the package registry -Version required: >= 0.0.0 +no package named `nonexistent` found (required by `foo`) +location searched: the package registry +version required: >= 0.0.0 ")); }) @@ -196,9 +196,9 @@ test!(update_registry { assert_that(p.cargo_process("build"), execs().with_status(101).with_stderr("\ -No package named `notyet` found (required by `foo`). -Location searched: the package registry -Version required: >= 0.0.0 +no package named `notyet` found (required by `foo`) +location searched: the package registry +version required: >= 0.0.0 ")); // Add the package and commit -- 2.30.2